#include "sort.h"

void ShellSort(vector<int>& vc){
  int gap = vc.size();
  while(gap > 1)
  {
    gap = gap/3+1;
    
    for(int i = 0; i<vc.size()-gap; ++i)
    {
      int end = i;
      int x = vc[end+gap];
      while(end >= 0)
      {
        if(x < vc[end])
        {
          vc[end+gap] = vc[end];
          end-=gap;
        }
        else{
          break;
        }
      }
      vc[end+gap] = x;
    }
  }
}
